1. Field of the Invention
The present invention relates in general to a data processing system and, in particular, to a superscalar processor. Still more particularly, the present invention relates to a superscalar processor and method for improving the accuracy of predictions of branch instruction destinations utilizing a cache including confirmation bits.
2. Description of the Related Art
Most architectures include branch instructions whose targets cannot be calculated from the address of the branch and the instruction itself. A branch (conditional or unconditional) whose target address is stored in a separate register and cannot be: calculated from the address of the instruction and the instruction itself is referred to here as an address-predictable branch instruction. For example, in the PowerPC (TM) architecture, the target address for xe2x80x9cBranch Conditional to Link Registerxe2x80x9d (BCLR) or xe2x80x9cBranch Conditional to Link Register and Linkxe2x80x9d (BCLRL) instructions is found in the Link Register (LR), and the target address for xe2x80x9cBranch Conditional to Count Registerxe2x80x9d (BCCTR) or xe2x80x9cBranch Conditional to Count Register and Linkxe2x80x9d (BCCTRL) instructions is found in the Count Register (CTR). The Link Register and Count Register are special purpose registers in the PowerPC architecture which are used mainly for storing the address of these instructions.
The architecture guarantees that these special-purpose registers will contain the requisite target address for an address-predictable branch when the instruction immediately prior to the address-predictable branch completes. An S instruction completes when a completion signal is received from the completion unit. In a deeply-pipelined microprocessor, an instruction is usually fetched many cycles prior to its execution and subsequent completion. Since the completion of this prior instruction usually lags the fetching of the instructions following the address-predictable branch by many cycles, there is a need to be able to predict the target of such branches with high accuracy.
A cache, which is a small amount of memory, may be maintained within a processor to store the predicted target addresses for such address-predictable branches.
A programmer writes code in a particular sequence. The code may include various branch, or jump, instructions. Branch instructions cause a departure during the execution of instructions from the original sequential order of the instructions. One method for increasing the speed of execution of instructions is to predict the likely outcome of the execution of a branch instruction. A prediction is made as to whether or not a branch will be taken the next time this branch instruction is executed.
A cache may be maintained within a processor which is a small amount of memory which includes a predicted destination for a particular type of branch instruction. This particular type of branch instruction is an address-predictable branch instruction whose target address is stored in a separate register, such as the cache described above, and whose target address cannot be calculated from the instruction itself.
The cache includes a plurality of entries. Each branch instruction will be associated with one of the entries. When a branch instruction is fetched, the entry of the cache associated with this branch instruction is read to determine the predicted destination for this branch.
Typically, after the branch is executed, if the actual branch destination was different from the predicted branch destination, the appropriate entry of the cache will be updated to include the actual destination. However, a problem can arise when the branch instruction continues to branch consecutively between a more common destination and a less common destination. For example, if a branch instruction first branches to a destination xe2x80x9cAxe2x80x9d, then to destination xe2x80x9cBxe2x80x9d, and then back to destination xe2x80x9cAxe2x80x9d, and continuing with this pattern, it is clear that the cache will always contain an incorrect prediction. After the branch to xe2x80x9cBxe2x80x9d, the entry of the cache will be updated to include xe2x80x9cBxe2x80x9d as the predicted destination. Thereafter, after the next branch to xe2x80x9cAxe2x80x9d, the cache will again be updated to predict xe2x80x9cAxe2x80x9d as the destination. For the example given, the cache will always mispredict the destination of this branch instruction.
Therefore a need exists for a data processing system and method for improving the accuracy of predictions of destinations of a particular type of address-predictable branch instructions utilizing a cache.
A superscalar processor and method are disclosed for improving the accuracy of predictions of a destination of a branch instruction utilizing a cache. The cache is established including multiple entries. Each of multiple branch instructions are associated with one of the entries of the cache. One of the entries of the cache includes a stored predicted destination for the branch instruction associated with this entry of the cache. The predicted destination is a destination the branch instruction is predicted to branch to upon execution of the branch instruction. The stored predicted destination is updated in the one of the entries of the cache only in response to two consecutive mispredictions of the destination of the branch instruction, wherein the two consecutive mispredictions were made utilizing the one of the entries of the cache.
The above as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.